package cn.iktz.mather.know.common;

import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

import org.apache.commons.io.IOUtils;

/**
 * 简易字典树实现
 */
public class TrieTreeBuilder {

	private TrieNode rootNode;
	private static TrieTreeBuilder builder = TrieTreeBuilder.newBuilder();

	public TrieTreeBuilder() {
		try {

			this.rootNode = new TrieNode(null, null);
			InputStream resourceAsStream = Thread.currentThread().getContextClassLoader()
					.getResourceAsStream("data/suggest.txt");
			List<String> words = IOUtils.readLines(new InputStreamReader(resourceAsStream));
			TreeSet<String> treeSet = new TreeSet<>(words);
			for (String word : treeSet) {
				addString(word);
			}
		} catch (Exception e) {
			e.printStackTrace();
		}

	}

	public static TrieTreeBuilder newBuilder() {
		return new TrieTreeBuilder();
	}

	public void build(Set<String> treeSet) {
		for (String word : treeSet) {
			builder.addString(word);
		}
	}

	public static List<String> suggest(String keyword) {
		return builder.getKeyWordsByPrefix(keyword);
	}

	/**
	 * 将关键字添加到Trie树中
	 * 
	 * @param keyWord
	 * @return
	 */
	public TrieTreeBuilder addString(String keyWord) {
		TrieNode node = rootNode;
		for (int i = 0; i < keyWord.length(); i++) {
			Character c = keyWord.charAt(i);
			node = node.addCharacter(c);
		}
		node.setIfWord(true);
		return this;
	}

	/**
	 * 根据关键字获取Trie树的全部节点
	 * 
	 * @param findStr
	 * @return
	 */
	public List<String> getKeyWordsByPrefix(String findStr) {
		List<String> suggestList = new ArrayList<String>();
		TrieNode findNode = rootNode;
		for (int i = 0; i < findStr.length(); i++) {
			Character c = findStr.charAt(i);
			findNode = findNode.getCharacter(c);
			if (findNode == null) {
				break;
			}
		}
		if (findNode == null) {
			return null;
		}
		if (findNode.isIfWord()) {
			suggestList.add(findStr);
		}
		getAllSubNodes(findNode, findStr, suggestList);
		return suggestList;
	}

	/**
	 * 递归遍历全部节点
	 * 
	 * @param node
	 * @param prefix
	 * @param suggestList
	 */
	private void getAllSubNodes(TrieNode node, String prefix, List<String> suggestList) {
		Map<Character, TrieNode> map = node.getMap();
		if (map != null) {
			Set<Character> keySet = map.keySet();
			List<TrieNode> nodeList = new ArrayList<TrieNode>();
			for (Character c : keySet) {
				nodeList.add(map.get(c));
			}
			for (TrieNode subNode : nodeList) {
				Character m = subNode.getCharacter();
				String word = prefix + m;
				if (subNode.isIfWord()) {
					suggestList.add(word);
				}
				getAllSubNodes(subNode, word, suggestList);
			}

		}

	}
}